import java.util.Stack;

/*
 * @lc app=leetcode.cn id=503 lang=java
 *
 * [503] 下一个更大元素 II
 *
 * https://leetcode-cn.com/problems/next-greater-element-ii/description/
 *
 * algorithms
 * Medium (51.05%)
 * Likes:    68
 * Dislikes: 0
 * Total Accepted:    7.8K
 * Total Submissions: 15.3K
 * Testcase Example:  '[1,2,1]'
 *
 * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x
 * 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
 *
 * 示例 1:
 *
 *
 * 输入: [1,2,1]
 * 输出: [2,-1,2]
 * 解释: 第一个 1 的下一个更大的数是 2；
 * 数字 2 找不到下一个更大的数；
 * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
 *
 *
 * 注意: 输入数组的长度不会超过 10000。
 *
 */

// @lc code=start
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        if(n == 0)
            return new int[]{};
        int[] arr = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int j = 0; j < 1; j++) {
            for(int i = n-1; i > -1; i--) {
                if(stack.isEmpty()) {
                    arr[i] = -1;
                } else {
                    while(!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                        stack.pop();
                    }
                    arr[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
                }
                stack.add(i);
            }
        }

        return arr;
    }
}
// @lc code=end

